package com.leetcode;

/**
 * 75. 颜色分类
 *
 * @author fy
 * @date 2022/4/2 9:22
 */
public class Solution75 {

    private void swap(int[] nums, int index1, int index2) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }

    public void sortColors(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int n = nums.length;
        // [0, zeroIndex]存放0
        int zeroIndex = -1;
        // [twoIndex, n - 1]存放2
        int twoIndex = n;
        // 那么[zeroIndex + 1, i] 存放的就是1, 其中 i < towIndex
        for (int i = 0; i < twoIndex; ) {
            if (nums[i] == 1) {
                i++;
            } else if (nums[i] == 2) {
                swap(nums, --twoIndex, i);
            } else if (nums[i] == 0) {
                swap(nums, ++zeroIndex, i++);
            }
        }
    }

    /**
     * 三路快排
     *
     * @param nums
     */
    public void sortColors1(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int n = nums.length;
        // [0, zeroIndex]存放0
        int zeroIndex = -1;
        // [twoIndex, n - 1]存放2
        int twoIndex = n;
        // 那么[zeroIndex + 1, i] 存放的就是1, 其中 i < towIndex
        for (int i = 0; i < twoIndex; ) {
            if (nums[i] == 1) {
                i++;
            } else if (nums[i] == 2) {
                --twoIndex;
                int tmp = nums[i];
                nums[i] = nums[twoIndex];
                nums[twoIndex] = tmp;
            } else if (nums[i] == 0) {
                ++zeroIndex;
                int tmp = nums[i];
                nums[i] = nums[zeroIndex];
                nums[zeroIndex] = tmp;
                i++;
            }
        }
    }

    public void sortColors2(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int n = nums.length;
        int[] count = new int[3];
        for (int i = 0; i < n; i++) {
            count[nums[i]]++;
        }
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            int num = count[i];
            for (int j = index; num > 0; j++) {
                index++;
                num--;
                nums[j] = i;
            }
        }
    }

    public static void main(String[] args) {
//        int[] nums = new int[]{2, 0, 2, 1, 1, 0};
        int[] nums = new int[]{1, 1};
        new Solution75().sortColors(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
    }

}
